package com.ai.sort;

import java.util.Arrays;

/**
 * 插入排序算法实现
 * 插入排序是一种通过构建有序序列，逐步将未排序的元素插入到有序序列中的排序方法。
 * 插入排序通过逐个比较未排序元素与已排序元素，找到合适的位置进行插入。
 * 算法时间复杂度为 O(n²)，在数组接近有序时性能较好。
 */
public class InsertionSort {

    // 插入排序方法，接收一个整数数组，并返回排序后的数组
    public static int[] insertionSort(int[] arr) {

        // 从数组的第二个元素开始，因为我们默认第一个元素是有序的
        for (int i = 1; i < arr.length; i++) {

            // 预先保存当前需要插入的元素及其前一个已排序元素的索引
            int preIndex = i - 1;
            int currentIndex = arr[i];

            // 从已排序部分的最后一个元素向前扫描
            // 当当前元素小于前一个已排序元素时，需要将前一个元素向后移动一位
            while (preIndex >= 0 && currentIndex < arr[preIndex]) {
                arr[preIndex + 1] = arr[preIndex]; // 将已排序的元素向后移动
                preIndex--; // 向前移动到前一个已排序元素继续比较
            }

            // 找到合适的位置后，将当前元素插入到正确的位置
            arr[preIndex + 1] = currentIndex;
        }
        // 返回排好序的数组
        return arr;
    }
}